﻿																/*【算法1-2】排序*/

//// P2676 [USACO07DEC] Bookshelf B
//// https://www.luogu.com.cn/problem/P2676
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//const int N = 20000;
//int a[N];
//
//bool cmp(int a, int b)
//{
//	return a > b;
//}
//
//void solve()
//{
//	int n, b;
//	cin >> n >> b;
//	
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//	}
//
//	sort(a, a + n, cmp);
//	ll sum = 0;
//	int i;
//	for (i = 0; sum < b; i++)
//		sum += a[i];
//	cout << i << endl;
//}
//
//int main()
//{
//	solve();
//	return 0;
//}

//
//// P1152 欢乐的跳
//// https://www.luogu.com.cn/problem/P1152
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//const int N = 1000;
//int a[N];
//int gap[N];
//
//void solve()
//{
//	int n;
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//		if (i > 0)
//			gap[i] = abs(a[i] - a[i - 1]);
//	}
//
//	sort(gap, gap + n);
//	for (int i = 1; i <= n - 1; i++)
//	{
//		if (gap[i] == gap[i - 1])
//		{
//			cout << "Not jolly" << endl;
//			return;
//		}
//	}
//	cout << "Jolly" << endl;
//}
//
//int main()
//{
//	solve();
//	return 0;
//}




//// P1271 【深基9.例1】选举学生会
//// https://www.luogu.com.cn/problem/P1271
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//const int N = 2000000;
//int a[N];
//
//void solve()
//{
//	int n, m;
//	cin >> n >> m;
//	for (int i = 0; i < m; i++)
//		cin >> a[i];
//	sort(a, a + m);
//	for (int i = 0; i < m; i++)
//		cout << a[i] << " ";
//}
//
//int main()
//{
//	solve();
//	return 0;
//}


//// P1923 【深基9.例4】求第 k 小的数
//// https://www.luogu.com.cn/problem/P1923
//
//// 不用管重复数据！！！！！！！！！！！！！
//
//// 1、优先队列
//// 2、快排，注意有多个重复元素的情况 ------------> 要使用三向切分快速排序
///*
//思路 3 (100pts)：O(n)
//C++ 的宝库：STL
//
//在 STL 里有一个神奇的函数 nth_element。
//
//它的用法是 nth_element(a+x,a+x+y,a+x+len);。
//
//执行之后数组a 下标x 到x+y−1的元素都小于a[x+y]，下标x+y+1 到x+len−1 的元素 都大于a[x+y]，但不保证数组有序。此时a[x+y] 就是数组区间
//x 到x+len−1 中第y 小的数，当然也可以自己定义cmp 函数。
//
//结论：差不多就是将我们的思路 2 做了一遍。
//
//nth_element 的时间复杂度是O(n) 的，不过 STL 常数普遍较大……但还是能过此题。
//*/
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//const int N = 5000000;
//int a[N];
//int n, k;
//
//// STL中find的时间复杂度：O(N^2)
//// 会TLE，因为n是5e6，n^2后是5e12 > 5e8
//// 空间复杂度：O(N)，虽然a是在全局，但是它是程序运行时占用的额外空间\
//
//// unordered_map的insert和find的平均复杂度都是O(1)
//
//void solve1()
//{
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//	}
//	sort(a, a + n);
//	cout << a[k];
//}
//
//// 优先队列
//void solve2()
//{
//	// 注意优先队列的写法
//	// 这样子写才是升序，小根堆
//	// 默认大根堆，是降序
//	priority_queue<int, vector<int>, greater<int>>que;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//		que.push(a[i]);
//	}
//
//	/*注意这里没有k--，因为第0小的是a[0]*/
//	while (k--)
//		que.pop();
//	cout << que.top();
//}
//
//void quickSort(int left, int right, int k)
//{
//	int lt = left;
//	int gt = right;
//	int i = left + 1;
//	int key = a[lt];
//
//	while (i <= gt)
//	{
//		if (a[i] < key)
//			swap(a[i++], a[lt++]);
//		else if (a[i] > key)
//			swap(a[i], a[gt--]);
//		else
//			i++;
//	}
//
//	if (k < lt)
//		quickSort(left, lt - 1, k);
//	else if (k > lt)
//		quickSort(lt + 1, right, k);
//	else
//		return;
//}
//
//// 快速排序
//void solve3()
//{
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//	}
//	quickSort(0, n - 1, k);
//	cout << a[k];
//}
//
//// nth_element
//void solve4()
//{
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//	}
//
//	nth_element(a, a + k, a + n);
//
//	cout << a[k];
//
//}
//
//int main()
//{
//	quickio;
//	cin >> n >> k;
//	solve4();
//	return 0;
//}


//// P1059 [NOIP2006 普及组] 明明的随机数
//// https://www.luogu.com.cn/problem/P1059
//
//// 去重 + 排序
// // 可以用set
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//const int N = 100;
//int a[N];
//
//void solve()
//{
//	int n;
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//	}
//	sort(a, a + n);
//	int i = 0, j = 1;
//	vector<int>ans;
//	// 双指针去重
//	while (i < n && j < n)
//	{
//		ans.push_back(a[i]);
//		while (j < n && a[i] == a[j])
//			j++;
//		i = j;
//		j++;
//	}
//	if (ans[ans.size() - 1] != a[n - 1])
//		ans.push_back(a[n - 1]);
//	cout << ans.size() << endl;
//	for (auto e : ans)
//		cout << e << ' ';
//}
//
//int main()
//{
//	solve();
//	return 0;
//}


//// P1093 [NOIP2007 普及组] 奖学金
//// https://www.luogu.com.cn/problem/P1093
//
//// 用来巩固C++
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//class Stu
//{
//	friend void solve();
//public:
//	bool operator>(Stu s) const
//	{
//		if (_total != s._total)
//			return _total > s._total;
//		else if (_C != s._C)
//			return _C > s._C;
//		else 
//			return key < s.key;
//	}
//private:
//	int key;
//	int _C;
//	int _M;
//	int _E;
//	int _total;
//};
//
//bool cmp(const Stu& s1, const Stu& s2)
//{
//	return s1 > s2;
//}
//
//void solve()
//{
//	int n;
//	cin >> n;
//	vector<Stu>v(n);
//	for (int i = 0; i < n; i++)
//	{
//		v[i].key = i + 1;
//		cin >> v[i]._C;
//		cin >> v[i]._M;
//		cin >> v[i]._E;
//		v[i]._total = v[i]._C + v[i]._M + v[i]._E;
//	}
//	int num = n >= 5 ? 5 : n;
//	sort(v.begin(), v.begin() + n, cmp);
//	for (int i = 0; i < num; i++)
//	{
//		cout << v[i].key << " " << v[i]._total << endl;
//	}
//}
//
//int main()
//{
//	solve();
//	return 0;
//}


//// P1781 宇宙总统
//// https://www.luogu.com.cn/problem/P1781
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//vector<pair<string, int>>v;
//
//template <typename T>
//bool cmp(T& it1, T& it2)
//{
//	string s1 = it1.first;
//	string s2 = it2.first;
//	if (s1.size() != s2.size())
//		return s1.size() > s2.size();
//	else
//		return s1 > s2;
//}
//
//void solve()
//{
//	int n;
//	cin >> n;
//	v.resize(n);
//	for (int i = 0; i < n; i++)
//	{
//		cin >> v[i].first;
//		v[i].second = i + 1;
//	}
//	sort(v.begin(), v.end(), cmp<pair<string,int>>);
//	cout << v[0].second << endl << v[0].first;
//}
//
//int main()
//{
//	solve();
//	return 0;
//}


//// P1116 车厢重组
//// https://www.luogu.com.cn/problem/P1116
//
//// 只要看前面有几个比该位大的数就好了
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//int a[10000];
//
//void solve()
//{
//	int n;
//	cin >> n;
//	int ans = 0;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//		for (int j = 0; j < i; j++)
//		{
//			if (a[j] > a[i])
//				ans++;
//		}
//	}
//	cout << ans << endl;
//}
//
//int main()
//{
//	solve();
//	return 0;
//}


//// P1068 [NOIP2009 普及组] 分数线划定
//// https://www.luogu.com.cn/problem/P1068
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//struct Peo
//{
//	int k;
//	int s;
//};
//
//bool cmp(const Peo& p1, const Peo& p2)
//{
//	if (p1.s != p2.s)
//		return p1.s > p2.s;
//	else
//		return p1.k < p2.k;
//}
//
//void solve()
//{
//	int n, m;
//	cin >> n >> m;
//	vector<Peo>v(n);
//	for (int i = 0; i < n; i++)
//	{
//		cin >> v[i].k >> v[i].s;
//	}
//
//	sort(v.begin(), v.end(), cmp);
//
//	int key = v[v.size() - 1].s;
//
//	/**/
//	if (m * 1.5 < n)
//	{
//		key = v[m * 1.5 - 1/**/].s;
//		for (int i = 0; i < n; i++)
//		{
//			if (v[i].s < key)
//			{
//				v.erase(v.begin() + i, v.end());
//				break;
//			}
//		}
//	}
//	cout << key << " " << v.size() << endl;;
//	for (int i = 0; i < v.size(); i++)
//		cout << v[i].k << " " << v[i].s << endl;
//}
//
//int main()
//{
//	solve();
//	return 0;
//}


//// P5143 攀爬者
//// https://www.luogu.com.cn/problem/P5143
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//struct ZB
//{
//	int x;
//	int y;
//	int z;
//	double b;
//};
//
//bool cmp(ZB z1, ZB z2)
//{
//	return z1.z < z2.z;
//}
//
//void solve()
//{
//	double sum = 0.0;
//	int n;
//	cin >> n;
//	vector<ZB>v(n);
//	for (int i = 0; i < n ; i++)
//	{
//		cin >> v[i].x >> v[i].y >> v[i].z;
//	}
//	sort(v.begin(), v.end(), cmp);
//
//	for (int i = 0; i < n - 1; i++)
//	{
//		sum += sqrt((v[i + 1].x - v[i].x) * (v[i + 1].x - v[i].x)
//			+ (v[i + 1].y - v[i].y) * (v[i + 1].y - v[i].y)
//			+ (v[i + 1].z - v[i].z) * (v[i + 1].z - v[i].z));
//	}
//	printf("%.3f\n", sum);
//}
//
//int main()
//{
//	solve();
//	return 0;
//}


//// P1104 生日
//// https://www.luogu.com.cn/problem/P1104
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//struct Stu
//{
//	string name;
//	int year;
//	int month;
//	int day;
//};
//
//bool cmp(Stu s1, Stu s2)
//{
//	if (s1.year != s2.year)
//		return s1.year < s2.year;
//	if (s1.month != s2.month)
//		return s1.month < s2.month;
//	if (s1.day != s2.day)
//		return s1.day < s2.day;
//
//	return false;/**/
//}
//
//void solve()
//{
//	int n;
//	cin >> n;
//	vector<Stu>v(n);
//	for (int i = 0; i < n; i++)
//	{
//		cin >> v[i].name >> v[i].year >> v[i].month >> v[i].day;
//	}
//	sort(v.begin(), v.end(), cmp);
//	for (int i = 0; i < n; i++)
//	{
//		cout << v[i].name << endl;
//	}
//}
//
//int main()
//{
//	solve();
//	return 0;
//}